package E_2024;

import java.util.Arrays;
import java.util.Comparator;

/*
    某云短信厂商，为庆祝国庆，推出充值优惠活动。
    现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
输入描述
    第一行客户预算M，其中 0 ≤ M ≤ 10^6
    第二行给出售价表， P1, P2, … Pn , 其中 1 ≤ n ≤ 100 ,
    Pi为充值 i 元获得的短信条数。
    1 ≤ Pi ≤ 1000 , 1 ≤ n ≤ 100
输出描述：
    最多获得的短信条数
示例1：
    输入：
    6
    10 20 30 40 60
    输出：
    70
    说明：
    分别充值1元和5元，可以获得10+60条短信，共70条，最大。
示例2：
    15
    10 20 30 40 60 60 70 80 90 150
    输出：
    210
    分别充值10元和5元，可以获得150+60条短信，共210条，最大。
 */
public class E_200_6 {
    public static void main(String[] args) {
        System.out.println(ans(new int[]{10,20,30,40,60,60,70,80,90,150},15));
        System.out.println(ans(new int[]{10,20,30,40,60},6));
    }
    // 动态规划
    public static int ans(int[] nums, int cents){
        int[][] temp = new int[cents+1][nums.length+1];
        for (int i = 1; i <= cents; i++) {
            for (int k = 1; k <= nums.length; k++) {
                if (i >= k) temp[i][k] = Math.max(temp[i-k][k] + nums[k-1], temp[i][k-1]);
                else temp[i][k] = temp[i][k-1];
            }
        }
        for (int[] ints : temp) {
            System.out.println(Arrays.toString(ints));
        }
        return temp[cents][nums.length];
    }
    // 数学问题，排序
    public static int ans1(int[] nums, int cents){
        int[][] temp = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            temp[i][0] = i+1;
            temp[i][1] = nums[i];
        }
        Arrays.sort(temp, Comparator.comparing(a -> ((double)a[1])/a[0]));
//        for (int[] ints : temp) {
//            System.out.println(ints[0] + " " + ints[1]);
//        }
        int ans = 0;
        int index = nums.length - 1;
        while(cents > 0){
            while (cents >= temp[index][0]) {
                ans += temp[index][1];
                cents -= temp[index][0];
            }
            index--;
        }
        return ans;
    }
}
